package com.xyj.week05;

import com.xyj.common.TreeNode;

/**
 * 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
 *
 * 二叉树的根是数组 nums 中的最大元素。
 * 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
 * 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
 * 返回有给定数组 nums 构建的 最大二叉树 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/maximum-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T5 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums,0,nums.length-1);
    }

    public TreeNode build(int []nums,int left,int right){
        //base case
        if(left>right) {
            return null;
        }
        //找到最大值和最大值对应的索引
        int maxValue=Integer.MIN_VALUE;
        int index=-1;
        for(int l=left;l<=right;l++){
            if(nums[l]>maxValue){
                maxValue=nums[l];
                index=l;
            }
        }
        //构造根节点
        TreeNode root=new TreeNode(maxValue);
        //左右分别遍历
        root.left=build(nums,left,index-1);
        root.right=build(nums,index+1,right);
        return root;
    }
}

